#include "route.h"

// 格式化地图
void ClearMap(Map *map)
{
    assert(map);

    map->vexnum = map->arcnum = 0;
    memset(map->vexs, 0, sizeof(map->vexs));

    for (int j = 0; j < MVNum; j++)
    {
        for (int k = 0; k < MVNum; k++)
        {
            map->arcs[j][k] = MAX;
        }
    }
}

// 清除所有道路
void ClearArc(Map *map)
{
    assert(map);
    for (int i = 0; i < MVNum; i++)
    {
        for (int j = 0; j < MVNum; j++)
        {
            map->arcs[i][j] = MAX;
        }
    }
    map->arcnum = 0;
}

// 加载文件信息到地图
void LoadMap(const char *filename, Map *map)
{
    assert(map);
    // FILE *fopen( const char *filename, const char *mode );
    FILE *fp = fopen(filename, "r");
    if (fp == NULL)
    {
        perror("LoadMap::fopen");
        exit(1);
    }
    // 读取顶点数(文件为空==0 不空==1 >1说明出错)
    // int fscanf( FILE *stream, const char *format [, argument ]... );
    if (fscanf(fp, "%d", &(map->vexnum)) > 1)
    {
        perror("LoadMap::fscanf_vexnum");
        fclose(fp);
        return;
    }
    // 读取顶点信息
    for (int i = 0; i < map->vexnum; i++)
    {
        if (fscanf(fp, "%s %d %d", map->vexs[i].name, &map->vexs[i].x, &map->vexs[i].y) != 3)
        {
            perror("LoadMap::fscanf_vexs[Num]");
            fclose(fp);
            return;
        }
        // char *fgets(char *s, int size, FILE *stream);
        fgets(map->vexs[i].intro, IntroLen, fp);
    }
    // 读取边数
    if (fscanf(fp, "%d", &map->arcnum) > 1)
    {
        perror("LoadMap::fscanf_arcnum");
        fclose(fp);
        return;
    }
    // 读取邻接矩阵
    for (int i = 0; i < map->vexnum; i++)
    {
        for (int j = 0; j < map->vexnum; j++)
        {
            if (fscanf(fp, "%d", &map->arcs[i][j]) > 1)
            {
                perror("LoadMap::fscanf_arcs[Num][Num]");
                fclose(fp);
                return;
            }
        }
    }
    fclose(fp);
    fp = NULL;
    cout << endl
         << ":::::::::::: 加载文件成功! ::::::::::::::" << endl
         << endl;
}

// 初始化地图
void InitMap(const char *filename, Map *map)
{
    assert(map);

    ClearMap(map);

    LoadMap(filename, map);
}

// 传地点名称 返回地点对应的vexs数组下标 不存在返回-1
int GetIndex(const Map *map, string &str)
{
    assert(map);
    int i = 0;
    for (i = 0; i < map->vexnum; i++)
    {
        if (!strcmp(map->vexs[i].name, str.c_str()))
            return i;
    }
    return -1;
}

// 检查输入坐标是否重复
bool Check_Coordinate(const Map *map, int x, int y)
{
    assert(map);
    for (int i = 0; i < map->vexnum; i++)
    {
        if (x == map->vexs[i].x && y == map->vexs[i].y)
        {
            return false; // 重复
        }
    }
    return true; // 不重复
}

// 传两个地点的下标 判断某条路是否存在
bool ExistingArc(const Map *map, int start, int b)
{
    assert(map);
    if (map->arcs[start][b] != MAX)
        return true;
    else
        return false;
}

// 已知两地点求距离[向上取整]
int CalDistance(const Map *map, const int start, const int b)
{
    double dist = sqrt(pow(map->vexs[start].x * Unit - map->vexs[b].x * Unit, 2) + pow(map->vexs[start].y * Unit - map->vexs[b].y * Unit, 2));

    // 向上取整1.0 ==> 隐式类型转换可用static_cast [不能用于两个不相关的类型进行转换]
    // int distance = static_cast<int>(dist) + (dist > static_cast<int>(dist) ? 1 : 0);

    // 向上取整2.0 调用库函数double std::ceil(double x);
    int distance = static_cast<int>(std::ceil(dist));

    return distance;
}

// 矩阵判满
bool Full_Matrix(const Map *map)
{
    assert(map);
    for (int i = 0; i < MVNum; i++)
    {
        for (int j = 0; j < MVNum; j++)
        {
            if (map->arcs[i][j] == MAX)
            {
                return false; // 不满
            }
        }
    }
    return true; // 满
}

// 矩阵判空
bool Empty_Matrix(const Map *map)
{
    assert(map);
    for (int i = 0; i < MVNum; i++)
    {
        for (int j = 0; j < MVNum; j++)
        {
            if (map->arcs[i][j] != MAX)
                return false; // 不空
        }
    }
    return true;
}

// 增加地点信息
void AddVexMap(Map *map)
{
    assert(map);
    if (map->vexnum == MVNum)
    {
        printf("地点信息已满, 无法增加地点\n");
        return;
    }

    // 增加信息
    string str;
    do
    {
        printf("地点名称:>");
        cin >> str;
        if (GetIndex(map, str) != -1)
            cout << endl
                 << "地图中已存在同名地点,请重新输入" << endl
                 << endl;
    } while (GetIndex(map, str) != -1);

    strcpy(map->vexs[map->vexnum].name, str.c_str());

    printf("地点简介:>");
    getchar();
    // char *fgets(char *s, int size, FILE *stream);
    fgets(map->vexs[map->vexnum].intro, IntroLen, stdin);

    int x, y;
    do
    {
        printf("地点坐标[0, 9]>:");
        cin >> x >> y;
        if (x < 0 || x > 9 || y < 0 || y > 9)
            cout << endl
                 << "坐标越界, 请在给定范围内确定坐标" << endl
                 << endl;
        if (Check_Coordinate(map, x, y) == false)
            cout << endl
                 << "地图中已存在相同坐标,请重新输入" << endl
                 << endl;
    } while (Check_Coordinate(map, x, y) == false || x < 0 || x > 9 || y < 0 || y > 9);

    map->vexs[map->vexnum].x = x;
    map->vexs[map->vexnum].y = y;

    map->vexnum++;
    cout << endl
         << "++++++++++++  成功增加地点!  ++++++++++++" << endl
         << endl;

    SaveMap(filename, map);
}

// 增加道路信息
void AddArcMap(Map *map)
{
    assert(map);
    if (Full_Matrix(map) == true)
    {
        cout << "道路信息已满, 请扩大邻接矩阵容量!" << endl;
        return;
    }

    string stra, strb;
    int start, b;

    do
    {
        printf("地点one>:");
        cin >> stra;
        start = GetIndex(map, stra);
        if (start == -1)
            cout << "地图中无"
                 << stra
                 << "地点,请重新输入" << endl;
    } while (start == -1);

    do
    {
        printf("地点two>:");
        cin >> strb;
        b = GetIndex(map, strb);
        if (b == -1)
            cout << "地图中无"
                 << strb
                 << "地点,请重新输入" << endl;
    } while (b == -1);

    // 道路查重
    if (map->arcs[start][b] != MAX)
    {
        cout << "地图中已存在该道路!" << endl;
        return;
    }

    // 存入道路长度
    map->arcs[start][b] = map->arcs[b][start] = CalDistance(map, start, b);

    map->arcnum++;

    cout << endl
         << "++++++++++++  成功增加道路!  ++++++++++++" << endl
         << endl;
    SaveMap(filename, map);
}

// 删除某个地点
void DelVexMap(Map *map)
{
    assert(map);
    // 判空
    if (map->vexnum == 0)
    {
        cout << "不存在可删除的地点!" << endl;
        return;
    }

    // delete vexs[Num]
    int index;
    string str;
    do
    {
        cout << "请输入您要删除的地点名称:" << endl;
        cin >> str;

        index = GetIndex(map, str); // 获取地点对应的vexs数组下标
        if (index == -1)
        {
            cout << "地图中不存在您想要删除的地点!" << endl;
            cout << "[重新输入]";
        }
    } while (index == -1);

    //////////////  更新邻接矩阵  //////////////////////////

    // 1.删除该地点通向的路
    for (int i = 0; i < MVNum; i++)
    {
        if (map->arcs[index][i] != MAX)
        {
            map->arcs[index][i] = map->arcs[i][index] = MAX;
            map->arcnum--;
        }
    }

    // 2.更新因移动造成索引改变的道路信息
    for (int i = index + 1; i < map->vexnum; i++)
    {
        for (int j = 0; j < map->vexnum; j++)
        {
            if (map->arcs[i][j] != MAX)
            {
                // 需要更新
                int objTo = map->arcs[i][j];
                map->arcs[j][i] = map->arcs[i][j] = MAX;

                // 确定i > index 只需要分析j的范围
                if (0 < j < index)
                {
                    map->arcs[i - 1][j] = map->arcs[j][i - 1] = objTo;
                }
                else if (j > index)
                {
                    map->arcs[i - 1][j - 1] = map->arcs[j - 1][i - 1] = objTo;
                }
            }
        }
    }

    // 清空原地点
    memset(&(map->vexs[index]), 0, sizeof(map->vexs[index]));

    // 不是尾删 需要移动数据
    if (index != map->vexnum - 1)
    {
        for (int i = index + 1; i < map->vexnum; i++)
        {
            map->vexs[i - 1] = map->vexs[i];
        }
    }

    map->vexnum--;
    printf("\n+++++++++++  该地点已被删除!  +++++++++++\n");
    SaveMap(filename, map);
}

// 删除某个道路
void DelArcMap(Map *map)
{
    assert(map);
    // 判空
    if (Empty_Matrix(map))
    {
        cout << "不存在可删除的道路!" << endl;
        return;
    }

    // 判道路首尾合理
    cout << "请输入您要删除的道路首端名称>:" << endl;
    string stra;
    int ai;
    do
    {
        cin >> stra;
        ai = GetIndex(map, stra);
        // 判存在
        if (ai == -1)
        {
            cout << "地图中不存在该地点!" << endl;
            cout << "请重新输入>:";
        }
    } while (ai == -1);

    cout << "请输入您要删除的道路尾端名称>:" << endl;
    string strb;
    int bi;
    do
    {
        cin >> strb;
        bi = GetIndex(map, strb);
        // 判存在
        if (bi == -1)
        {
            cout << "地图中不存在该地点!" << endl;
            cout << "请重新输入>:";
        }
    } while (bi == -1);

    // 判道路存在
    if (!ExistingArc(map, ai, bi))
    {
        cout << "该路不存在, 无法删除!" << endl;
        return;
    }

    // 删除指定道路
    map->arcs[ai][bi] = map->arcs[bi][ai] = MAX;
    map->arcnum--;
    printf("\n+++++++++++  该道路已被删除!  +++++++++++\n");
    SaveMap(filename, map);
}

// 查找某个地点
void SearchVexMap(const Map *map)
{
    assert(map);
    if (map->vexnum == 0)
    {
        cout << "地点信息为空, 无法查找!" << endl;
        return;
    }

    string str;
    int index = 0;
    do
    {
        cout << "请输入要查找的地点名称>:" << endl;
        cin >> str;
        index = GetIndex(map, str);
        if (index == -1)
        {
            cout << "所查找地点不存在!" << endl;
            cout << "[重新输入]";
        }
    } while (index == -1);

    cout << "所查找地点名称:" << map->vexs[index].name << endl;
    cout << "所查找地点简介:" << map->vexs[index].intro;
    cout << "所查找地点坐标:(" << map->vexs[index].x << ", " << map->vexs[index].y << ")" << endl;
}

// 查找某个道路
void SearchArcMap(const Map *map)
{
    assert(map);
    // 判空
    if (Empty_Matrix(map))
    {
        cout << "道路信息为空, 无法查找!" << endl;
        return;
    }

    // 判道路首尾合理
    cout << "请输入您要查找的道路首端名称>:" << endl;
    string stra;
    int ai;
    do
    {
        cin >> stra;
        ai = GetIndex(map, stra);
        // 判存在
        if (ai == -1)
        {
            cout << "地图中不存在该地点!" << endl;
            cout << "请重新输入>:";
        }
    } while (ai == -1);

    cout << "请输入您要查找的道路尾端名称>:" << endl;
    string strb;
    int bi;
    do
    {
        cin >> strb;
        bi = GetIndex(map, strb);
        // 判存在
        if (bi == -1)
        {
            cout << "地图中不存在该地点!" << endl;
            cout << "请重新输入>:";
        }
    } while (bi == -1);

    // 判道路存在
    if (ExistingArc(map, ai, bi))
    {
        cout << "查找成功, 该条道路信息如下:" << endl;
        cout << map->vexs[ai].name << " <===" << map->arcs[ai][bi] << "===> " << map->vexs[bi].name << endl;
    }
    else
    {
        cout << "查找失败, 地图中不存在该路!" << endl;
    }
    return;
}

// 修改vexs数组中下标为index的地点信息
void ModifyVexMsg(Map *map, int index)
{
    enum Option
    {
        EXIT,
        INTRODUCTION,
        NAME,
        COORDINATE
    };

    string msg;
    int x, y;
    int option = 0;
    do
    {
        cout << endl
             << "请选择您要修改的信息>:" << endl
             << endl;
        printf("*****************************************\n");
        printf("*****  0. exit    1. introduction  ******\n");
        printf("*****  2. name    3. coordinate    ******\n");
        printf("*****************************************\n");

        cin >> option;
        switch (option)
        {
        case INTRODUCTION:
            cout << "请输入新简介>:";
            getchar();
            fgets(map->vexs[index].intro, IntroLen, stdin); // char *fgets(char *s, int size, FILE *stream);
            cout << endl
                 << "~~~~~~~~~  简介修改成功!  ~~~~~~~~" << endl;
            break;
        case NAME:
            memset(&(map->vexs[index].name), 0, sizeof(map->vexs[index].name));
            do
            {
                cout << "请输入新名称>:";
                cin >> msg;
                if (GetIndex(map, msg) != -1)
                    cout << endl
                         << "地图中已存在同名地点,请重新输入" << endl
                         << endl;
            } while (GetIndex(map, msg) != -1);

            strcpy(map->vexs[index].name, msg.c_str());
            cout << endl
                 << "~~~~~~~~~  名称修改成功!  ~~~~~~~~" << endl;
            break;
        case COORDINATE:
            cout << "请输入新坐标>:";

            do
            {
                printf("地点坐标[0, 9]>:");
                cin >> x >> y;
                if (x < 0 || x > 9 || y < 0 || y > 9)
                    cout << endl
                         << "坐标越界, 请在给定范围内确定坐标" << endl
                         << endl;
                if (Check_Coordinate(map, x, y) == false)
                    cout << endl
                         << "地图中已存在相同坐标,请重新输入" << endl
                         << endl;
            } while (Check_Coordinate(map, x, y) == false || x < 0 || x > 9 || y < 0 || y > 9);

            map->vexs[index].x = x;
            map->vexs[index].y = y;
            cout << endl
                 << "~~~~~~~~~  坐标修改成功!  ~~~~~~~~" << endl;
            break;
        case EXIT:
            cout << endl
                 << "~~~~~~~~~  修改信息成功!  ~~~~~~~~~" << endl;
            break;
        default:
            cout << "选择错误!" << endl;
            break;
        }
    } while (option);
}
// 修改某个地点
void ModifyVexMap(Map *map)
{
    assert(map);
    if (map->vexnum == 0)
    {
        cout << "不存在可修改的地点!" << endl;
        return;
    }
    int index;
    string str;
    do
    {
        cout << "请输入您要修改的地点名称:" << endl;
        cin >> str;

        index = GetIndex(map, str); // 获取地点对应的vexs数组下标
        if (index == -1)
        {
            cout << "地图中不存在您想要修改的地点!" << endl;
            cout << "[重新输入]";
        }
    } while (index == -1);

    // 修改信息
    ModifyVexMsg(map, index);
    printf("\n+++++++++  该地点信息已被修改!  +++++++++\n");
    SaveMap(filename, map);
}

// // 修改某条道路长度 -- 道路长度取决于首尾坐标 不予修改
// void ModifyArcMap(Map *map)
// {
//     assert(map);
//     // 判空
//     if (Empty_Matrix(map))
//     {
//         cout << "不存在可修改的道路!" << endl;
//         return;
//     }

//     // 判道路首尾合理
//     cout << "请输入您要修改的道路首端名称>:" << endl;
//     string stra;
//     int ai;
//     do
//     {
//         cin >> stra;
//         ai = GetIndex(map, stra);
//         // 判存在
//         if (ai == -1)
//         {
//             cout << "地图中不存在该地点!" << endl;
//             cout << "请重新输入>:";
//         }
//     } while (ai == -1);

//     cout << "请输入您要修改的道路尾端名称>:" << endl;
//     string strb;
//     int bi;
//     do
//     {
//         cin >> strb;
//         bi = GetIndex(map, strb);
//         // 判存在
//         if (bi == -1)
//         {
//             cout << "地图中不存在该地点!" << endl;
//             cout << "请重新输入>:";
//         }
//     } while (bi == -1);

//     // 判道路存在
//     if (!ExistingArc(map, ai, bi))
//     {
//         cout << "该路不存在, 无法修改!" << endl;
//         return;
//     }
//     cout << "道路的新长度>:";
//     cin >> map->arcs[ai][bi];
//     printf("\n+++++++++  该道路长度已被修改!  +++++++++\n");
//     SaveMap(filename, map);
// }

// 打印地图中所有地点
void ShowVexMap(const Map *map)
{
    assert(map);
    if (map->vexnum == 0)
    {
        cout << "地点为空" << endl;
        return;
    }
    for (int i = 0; i < map->vexnum; i++)
    {
        cout << "地点" << i + 1 << ":" << endl;
        printf("名称: %-10s\n", map->vexs[i].name);
        printf("简介: %s", map->vexs[i].intro);
        cout << "坐标: (" << map->vexs[i].x << ", " << map->vexs[i].y << ")" << endl;
    }
}

// 打印地图中所有道路
typedef struct Road // 道路信息
{
    string from;
    string to;
    int distance;
} Road;
bool compareRoadLen(const Road &start, const Road &end) // 按照距离排序
{
    return start.distance < end.distance;
}
void ShowArcMap(const Map *map)
{
    assert(map);
    if (Empty_Matrix(map))
    {
        cout << "道路为空" << endl;
        return;
    }

    /*
    //无序输出道路 只输出下三角
    for (int i = 1; i < map->vexnum; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (map->arcs[i][j] != 0)
            {
                cout << map->vexs[i].name << " <===" << map->arcs[i][j] << "===> " << map->vexs[j].name << endl;
            }
        }
    }
    */

    vector<Road> routes;

    // 遍历上三角邻接矩阵
    for (int i = 0; i < map->vexnum; ++i)
    {
        for (int j = i + 1; j < map->vexnum; ++j)
        {
            if (map->arcs[i][j] != MAX) // 存在道路
            {
                routes.push_back({map->vexs[i].name, map->vexs[j].name, map->arcs[i][j]});
            }
        }
    }

    // 对道路距离进行排序
    //mysort(routes.begin(), routes.end(), compareRoadLen);
    sort(routes.begin(), routes.end(), compareRoadLen);

    // 输出道路信息
    for (const Road &route : routes)
    {
        cout << route.from << " <==" << route.distance << "==> " << route.to << endl;
    }
}

// 传坐标获取地点下标 坐标不是地点返回-1
int XYtoIndex(const Map *map, int X, int Y)
{
    int i;
    for (i = 0; i < map->vexnum; i++)
    {
        if (map->vexs[i].x == X && map->vexs[i].y == Y)
        {
            return i;
        }
    }
    return -1;
}
// 打印整个地图
void ShowMap(const Map *map)
{
    // 找到地图的最大x和y坐标 -- 定边界
    int maxX = 0, maxY = 0;
    for (int i = 0; i < map->vexnum; ++i)
    {
        maxX = max(maxX, map->vexs[i].x);
        maxY = max(maxY, map->vexs[i].y);
    }

    int index; // 由坐标获得的下标

    // 输出地图
    for (int y = maxY; y >= 0; y--)
    {
        for (int x = 0; x <= maxX; x++)
        {
            index = XYtoIndex(map, x, y);

            if (index == -1)
                printf("%-12s", " ");
            else
                printf("%-12s", map->vexs[index].name);
        }
        cout << endl; // 换行
    }
}

// 显示当前矩阵数据
void ShowMatrix(const Map *map)
{
    assert(map);
    for (int i = 0; i < MVNum; i++)
    {
        for (int j = 0; j < MVNum; j++)
        {
            if (j == MVNum - 1)
            {
                printf("%-4d\n", map->arcs[i][j] == MAX ? 0 : map->arcs[i][j]);
                // printf("%-4d\n", map->arcs[i][j]);
            }
            else
            {
                printf("%-4d ", map->arcs[i][j] == MAX ? 0 : map->arcs[i][j]);
                // printf("%-4d ", map->arcs[i][j]);
            }
        }
    }
}

// 保存文件信息到文件
void SaveMap(const char *filename, Map *map)
{
    assert(map);

    FILE *fp = fopen(filename, "w");
    if (fp == NULL)
    {
        perror("SaveMap::fopen_Error");
        return;
    }

    // 写入顶点数
    fprintf(fp, "%d\n", map->vexnum);

    // 写入顶点信息
    for (int i = 0; i < map->vexnum; i++)
    {
        fprintf(fp, "%s %d %d", map->vexs[i].name, map->vexs[i].x, map->vexs[i].y);
        // int fputs( const char *string, FILE *stream );
        fputs(map->vexs[i].intro, fp);
    }

    // 写入边数
    fprintf(fp, "%d\n", map->arcnum);

    // 写入邻接矩阵
    for (int i = 0; i < map->vexnum; i++)
    {
        for (int j = 0; j < map->vexnum; j++)
        {
            fprintf(fp, "%d ", map->arcs[i][j]);
        }
        fprintf(fp, "\n");
    }

    fclose(fp);
}

//////////////////////  最短路径  ////////////////////////////////

// 输出obj到其中一个dest的最短路径
void PrintPerPath(const Map *map, const vector<int> &prev, int dest)
{
    // end前无结点 ==> end此时为道路首端 直接输出
    if (prev[dest] == -1)
    {
        cout << map->vexs[dest].name;
    }
    else
    {
        int pre = prev[dest];
        // end前有其他结点 递归回溯至首结点停止
        PrintPerPath(map, prev, pre);
        cout << " <=" << map->arcs[pre][dest] << "=> ";
        cout << map->vexs[dest].name;
    }
}

// 输出从obj到达所有地点最短路径
void PrintShortest_Path(const Map *map, vector<Pair> &sortedPaths, vector<int> &objTo, vector<int> &prev)
{
    //  遍历sortedPaths 依次取出终点下标 输出总距离
    for (const auto &path : sortedPaths)
    {
        int dest = path.second;
        cout << "Sum=" << objTo[dest] << "::";

        // src到other有多条路 输出每条路 依次输出obj->dest的最短路径
        PrintPerPath(map, prev, dest);
        cout << endl;
    }
}

// 使用Dijkstra算法存储从obj到其他所有地点的最短路径
void Dijkstra(const Map *map, int obj, vector<int> &objTo, vector<int> &prev)
{ // objTo: obj到其他各顶点的最短简单路径的距离 prev: 从obj到other的最短路径中 other前驱顶点的标号
    // template<class T, class Container,  class Compare>
    priority_queue<Pair, vector<Pair>, greater<Pair>> pq; // class priority_queue; ==> 建小根堆
    objTo[obj] = 0;                                       // 点到自身距离为0
    pq.push({objTo[obj], obj});                           // obj点入队

    while (!pq.empty()) // 每轮过后 队列中存储 邻接的所有路的信息
    {
        int New = pq.top().second; // 队首即小根堆 堆头 ==> 当前队列中距离最小值 ==> 选最近的路
        pq.pop();

        for (int other = 0; other < map->vexnum; ++other)
        {
            int NewtoOther = map->arcs[New][other];

            if (NewtoOther != 0                            // 当other遍历至new时 距离为0 不进行更新
                && objTo[New] != MAX                       // 当obj到New无边时 不进行更新
                && objTo[New] + NewtoOther < objTo[other]) // 当由于New的加入 使得obj到other的距离缩短 ==> 更新
            {
                objTo[other] = objTo[New] + NewtoOther;

                prev[other] = New; // prev[other]: 从obj到other的最短路径中 other的前一个顶点的标号

                pq.push({objTo[other], other});
            }
        }
    }
}

// 计算从obj到其他所有地点的最短简单路径[递增输出]
void ShowShortest_Path(const Map *map)
{
    assert(map);

    if (map->vexnum == 0 || Empty_Matrix(map))
    {
        cout << "地图信息为空, 无法进行相应操作!" << endl;
        return;
    }

    string str;
    int obj;
    do
    {
        cout << "请输入源地点>:";
        cin >> str;
        cout << endl;
        obj = GetIndex(map, str);
        if (obj == -1)
        {
            cout << "输入的地点不存在!" << endl;
            cout << "[重新输入]";
        }
    } while (obj == -1);

    vector<int> objTo(map->vexnum, MAX); // obj到其他各顶点的距离 初始为MAX 更新后为obj到其他各顶点的最短简单路径的距离
    vector<int> prev(map->vexnum, -1);   // 从obj到other的最短路径中 other前驱顶点的标号 other前无顶点 存-1

    Dijkstra(map, obj, objTo, prev); // 调用Dijkstra之后objTo数组中的数据为obj到其他各顶点的最短简单路径的距离

    // for debug: 显示打印objTo和prev的数据
    /*
    cout << "prev[]: ";
        for (const auto &value : prev)
        {
            cout << value << " ";
        }
        cout << endl;
        cout << "objTo[]: ";
        for (const auto &value : objTo)
        {
            cout << value << " ";
        }
        cout << endl;
        cout << endl;
    */

    vector<Pair> sortedPaths; // 将{obj到other的距离,other} 存储至vector容器 ==> 使用sort函数
    for (int i = 0; i < map->vexnum; ++i)
    {
        if (i != obj            // 当i遍历至obj时 objTo[obj] 无意义 不存
            && objTo[i] != MAX) // 无路径不存
        {
            sortedPaths.push_back({objTo[i], i});
        }
    }

    // template <class RandomAccessIterator> 默认递增排序Pair的第一个参数
    // void sort (RandomAccessIterator first, RandomAccessIterator last);
    sort(sortedPaths.begin(), sortedPaths.end()); // 排序后为obj->other的最短路径的递增顺序

    PrintShortest_Path(map, sortedPaths, objTo, prev);

    cout << endl
         << "从 " << str << " 到其他所有地点的最短简单路径已显示完毕!" << endl
         << endl;
}

//////////////////////  最短路径   ////////////////////////////////

//////////////////////  最小生成树   ////////////////////////////////

// Prim算法生成最小生成树
void Prim(const Map *map, int src)
{
    int visited[MVNum]; // 记录other是否被访问
    int lowcost[MVNum]; // 记录other到最小生成树的最短距离
    int sum = 0;        // 最小生成树的总长度

    // visited[]数组初始为未访问
    memset(visited, 0, sizeof(visited));
    visited[src] = 1; // 电源点初始默认已加入到MST

    // lowcost[]数组初始记录other到电源点的最短距离
    for (int i = 0; i < map->vexnum; i++)
    {
        lowcost[i] = map->arcs[src][i];
    }

    // 总共还剩other个顶点未加入到MST
    int other = map->vexnum - 1;
    while (other--)
    {
        // 每想添加一个顶点到MST 都计算三个值

        int NewPath = MAX; // 即将加入MST的边的路长
        int NewBegin = 0;  // 即将加入MST的边的首端
        int NewEnd = 0;    // 即将加入MST的边的尾端

        // 设定已加入MST的为A类顶点 未加入MST的为B类顶点
        //  对于A类的每一顶点  进行轮询B类的每一顶点
        // 找到从B能够到A的一条最短路径作为MST的新边
        for (int i = 0; i < map->vexnum; i++)
        {
            // 如果i未被访问 跳过下面代码 执行下次循环
            // 目的: 找到一个已加入到MST的顶点
            if (!visited[i])
                continue;

            for (int j = 0; j < map->vexnum; j++)
            {
                // 找到一个未访问的顶点
                if (!visited[j] && map->arcs[i][j] < NewPath)
                {
                    NewPath = map->arcs[i][j];

                    // 记录下所增加的新边的两端
                    //(每次if都会更新 最后一次存入了最短可达路径的两端)
                    NewBegin = i;
                    NewEnd = j;
                }
            }
        }

        // 将新路的尾端即新加入A类的顶点设为已访问表示该顶点已加入到MST
        visited[NewEnd] = 1;

        sum += NewPath;

        // 输出此次新增的部分电路
        cout << map->vexs[NewBegin].name << " <==" << NewPath << "==> " << map->vexs[NewEnd].name << endl;
    }

    // 输出最小生成树的总长度
    cout << endl
         << "电路总长度 == " << sum << endl
         << endl;
}
// 最短通电线路 ==> MST
// 输出铺路规划+每条电路长度+电路总长度)
void Lay_Circuit(const Map *map)
{
    assert(map);

    string begin;
    int index;
    do
    {
        printf("请输入电源点>:");
        cin >> begin;
        index = GetIndex(map, begin);
        if (index == -1)
            cout << "地图中无"
                 << begin
                 << "地点,请重新输入" << endl;
    } while (index == -1);

    Prim(map, index);
    cout << endl;
}

//////////////////////  最小生成树   ////////////////////////////////

//////////////////// 过所有点距离最短  ////////////////////////////////////////////

// 将新道路信息添加到allPath
void AddNewPath(const Map *map, const vector<int> &prev, int dest, vector<int> &allPath)
{
    // end前有其他结点 递归回溯至首结点停止
    if (prev[dest] != -1)
    {
        int pre = prev[dest];

        AddNewPath(map, prev, pre, allPath);

        allPath.push_back(dest);
    }
    // end前无结点 ==> end此时为道路首端 无操作
}

// 输出整条道路
void PrintRoutes(const Map *map, int cur, vector<int> &allPath)
{
    for (const auto &index : allPath)
    {
        if (index == cur)
            cout << map->vexs[index].name;
        else
            cout << "---" << map->vexs[index].name;
    }
    cout << endl;
}

// 处理函数
void Handle(const Map *map, int obj)
{
    int cur = obj;
    int sum = 0;                              // 指定路线的总长度
    vector<int> allPath;                      // 存储指定路线
    vector<bool> visited(map->vexnum, false); // 访问状态数组

    allPath.push_back(obj); // cur已加入路线
    visited[obj] = true;    // cur已访问

    int other = map->vexnum - 1; // 还剩other个地点未加入
    while (other--)
    {
        vector<int> objTo(map->vexnum, MAX); // obj到其他各顶点的距离 初始为MAX 更新后为obj到其他各顶点的最短简单路径的距离
        vector<int> prev(map->vexnum, -1);   // 从obj到other的最短路径中 other前驱顶点的标号 other前无顶点 存-1

        // New的确定取决于obj即当前地点 把obj传给Dijkstra 计算obj到其他所有地点的最短路径
        Dijkstra(map, obj, objTo, prev);

        // 将obj到其他所有未被访问的地点的距离取最小值 作为NewPath
        vector<Pair> sortedPaths; // 将{obj到other的距离,other} 存储至vector容器 ==> 使用sort函数
        for (int i = 0; i < map->vexnum; ++i)
        {
            if (i != obj               // objTo[obj]  不存
                && objTo[i] != MAX     // 无路径不存
                && visited[i] == false // i已访问不存
            )
            {
                sortedPaths.push_back({objTo[i], i});
            }
        }

        // template <class RandomAccessIterator> 默认递增排序Pair的第一个参数
        // void sort (RandomAccessIterator first, RandomAccessIterator last);
        sort(sortedPaths.begin(), sortedPaths.end()); // 排序后为obj->other的最短路径的递增顺序

        // 确定了New  更新路线总长度
        visited[sortedPaths[0].second] = true;
        sum += sortedPaths[0].first;
        obj = sortedPaths[0].second;

        // 记录路线
        AddNewPath(map, prev, sortedPaths[0].second, allPath);
    }

    PrintRoutes(map, cur, allPath);
    cout << "总长度为: " << sum << endl;
    cout << endl;
}

// A地出发经过所有点且距离最短(可重复)
void PassAllVex_Path(const Map *map)
{
    string stra;
    int index;

    do
    {
        printf("请输入出发地>:");
        cin >> stra;
        index = GetIndex(map, stra);
        if (index == -1)
            cout << "地图中无"
                 << stra
                 << "地点,请重新输入" << endl;
    } while (index == -1);
    cout << "正在生成" << endl;

    Handle(map, index);
}

//////////////////// 过所有点距离最短  ////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////// 过所有点距离最短回到原点  ////////////////////////////////////////

// A地出发过所有点回到A点且距离最短(可重复)[demo]
void PassAllVex_Loop(const Map *map)
{
    string stra;
    int index;

    do
    {
        printf("请输入出发地>:");
        cin >> stra;
        index = GetIndex(map, stra);
        if (index == -1)
            cout << "地图中无"
                 << stra
                 << "地点,请重新输入" << endl;
    } while (index == -1);
    cout << "正在生成" << endl;

    // Demo(map, index);
}
